part of internal;

class DoublyLinkedList<Item> {
   Node<Item> _first;
   Node<Item> _last;
   Node<Item> _here;
   int _rec;
   int _len;

   // internal
   void _setRec (int n) {
      if (n < _rec) for (int i = _rec; i > n; i--) _here = _here.prev;
      if (n > _rec) for (int i = _rec; i < n; i++) _here = _here.next;
      _rec = n;
   }

   // generator
   DoublyLinkedList () {
      _rec = -1;
      _len = 0;
      if (dev) if (!valid) staErr(this);
   }

   // mutators
   void insert (int n, Item item) {
      if (dev) if (n > _len) argErr(n);
      Node<Item> tmp = new Node(item);
      // if empty
      if (_len == 0) {
         _first = tmp;
         _last = tmp;
         _here = tmp;
         _rec = 0;
         _len = 1;
         if (dev) if (!valid) staErr(this);
         return;
      }
      _setRec(n);
      // if inserting at start
      if (_rec == 0) {
         tmp.next = _first;
         _first.prev = tmp;
         _first = tmp;
         _here = tmp;
         _len++;
         if (dev) if (!valid) staErr(this);
         return;
      }
      // if inserting at end
      if (_rec == _len) {
         tmp.prev = _last;
         _last.next = tmp;
         _last = tmp;
         _here = tmp;
         _len++;
         if (dev) if (!valid) staErr(this);
         return;
      }
      Node<Item> befor = _here.prev;
      Node<Item> after = _here;
      tmp.prev = befor;
      befor.next = tmp;
      tmp.next = after;
      after.prev = tmp;
      _here = tmp;
      _len++;
      if (dev) if (!valid) staErr(this);
   }
   void delete (int n) {
      if (dev) if (n >= _len) argErr(n);
      _setRec(n);
      // if single node present
      if (_len == 1) {
         _first = null;
         _last = null;
         _here = null;
         _rec = -1;
         _len = 0;
         if (dev) if (!valid) staErr(this);
         return;
      }
      // if deleting first node
      if (_rec == 0) {
         _first = _first.next;
         _first.prev = null;
         _here = _first;
         _len--;
         if (dev) if (!valid) staErr(this);
         return;
      }
      // if deleting last node
      if (_rec == _len - 1) {
         _last = _last.prev;
         _last.next = null;
         _here = _last;
         _rec--;
         _len--;
         if (dev) if (!valid) staErr(this);
         return;
      }
      Node<Item> befor = _here.prev;
      Node<Item> after = _here.next;
      befor.next = after;
      after.prev = befor;
      _here = after;
      _len--;
      if (dev) if (!valid) staErr(this);
   }
   void replace (int n, Item item) {
      if (dev) {
         if (n == null) argErr(n);
         if (item == null) argErr(item);
         if (n >= _len) argErr(n);
      }
      _setRec(n);
      _here.item = item;
      if (dev) if (!valid) staErr(this);
   }

   // observers
   Item get first {
      if (dev) if (_len == 0) argErr('first');
      return _first.item;
   }
   Item get last {
      if (dev) if (_len == 0) argErr('last');
      return _last.item;
   }
   Item nth (int n) {
      if (dev) if (n >= _len) argErr(n);
      _setRec(n);
      return _here.item;
   }
   int get len => _len;

   // invariants
   bool get valid {
      if (_rec == null) return false;
      if (_len == null) return false;
      if (_len == 0) {
         if (_first != null) return false;
         if (_last != null) return false;
         if (_here != null) return false;
         if (_rec != -1) return false;
         return true;
      }
      else {
         if (_first == null) return false;
         if (_last == null) return false;
         if (_here == null) return false;
         if (_rec == -1) return false;
         if (_rec >= _len) return false;
         Node<Item> forw = _first;
         for (int i = 0; i < _len; i++) {
            if (i == _rec) if (forw != _here) return false;
            if (i == _len - 1) if (forw != _last) return false;
            forw = forw.next;
         }
         if (forw != null) return false;
         Node<Item> back = _last;
         for (int i = _len - 1; i >= 0; i--) {
            if (i == _rec) if (back != _here) return false;
            if (i == 0) if (back != _first) return false;
            back = back.prev;
         }
         if (back != null) return false;
         return true;
      }
   }

   // printing
   String toString () {
      StringBuffer tmp = new StringBuffer();
      Node<Item> trav = _first;
      for (int i = 0; i < _len; i++) {
         tmp.write('$i -> ${trav.item}');
         tmp.writeln();
         trav = trav.next;
      }
      return tmp.toString();
   }
}
